//方法1
//数组中每个元素都可以添加+ - 号，所以n和元素一共有2的n次方中添加方法，
//对应2n种不同表达式。如果表达式结果为target，则符合要求，计数器加1
//编译所有表达式，返回计数器

//类似DFS


//求解思路
//只用nums[i]以及它后面的数，也就是
//nums[i, i + 1, ..., n - 1]这些数，来凑出target，
//有多少种凑法
//1. 如果i == n，也就是说一个数都不给用，或者说用0个数来凑，
//自然只能凑出0了。
//这也就是递归的结束条件：
//当i == n时，如果target == 0，则有1种凑法，否则有0种凑法。


//2. 如果i < n，那么用nums[i, i + 1, ..., n - 1]这些数，
//来凑出target，可以分为下面两种情况：

//a. 如果nums[i]被用来做加法了，
//那接下来就要看看用nums[i + 1, ..., n - 1]这些数，
//来凑出target - nums[i]，有多少种凑法了；
//
//b. 如果nums[i]被用来做减法了，
//那接下来就要看看用nums[i + 1, ..., n - 1]这些数，
//来凑出target + nums[i]，有多少种凑法了
//把2.1和2.2两种情况的凑法的总数求出来，就是上面的问题的答案了


class Solution
{
public:
int count=0;
int findTargetSumWays(std::vector<int>& nums,int target)
{
    backtrack(nums,target,0,0);
    return count;
}
void backtrack(std::vector<int>& nums,int target,int index,int sum)
{
    if (index==nums.size())
    {
        if (sum==target)
        {
            count++;
        }
    }
    else
    {
        backtrack(nums,target,index+1,sum+nums[index]);
        backtrack(nums, target, index + 1, sum - nums[index]);
    }
}
};  











